package leetcode.d_1_99;

public class P92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null) {
            return head;
        }
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        ListNode tail = dummyNode;

        for (int i = 1; i < left; i++) {
            tail.next = head;
            tail = head;
            head = head.next;
        } // 此时head 指向了left， tail指向left前一个


        ListNode pre = null; // left->right反转后的头节点
        ListNode revTail = head; // 反转这一段的末尾节点，就是要反转的第一个节点

        for (int i=left; i<=right; i++) {
            ListNode next = head.next;
            head.next = pre;

            pre = head;
            head = next;
        }

        revTail.next = head; // 反转后的尾结点直接指向最后一段链表
        tail.next = pre; // 第一段接上第二段
        return dummyNode.next;
    }
}
